Most image sensors and displays generate or accept image signals in color raster scan format, in which pixels comprising a first horizontal line are generated or displayed sequentially (from left to right), and pixels comprising the next line are then generated or displayed sequentially (from left to right), and so on. In many conventional color image display devices, each pixel is driven by a set of three analog color component signals (a red, a green, and a blue color component signal). Typically, each analog color component signal is generated by processing a multi-bit digital data word in a digital-to-analog conversion circuit.
If a set of analog or digital image data in color raster scan format represents a monochrome image, the data are said to be in "line-scan" format. If a set of analog or digital data in color raster scan format represents a color image, the individual color component signals are typically interleaved.
It is well known to perform image compression on digital image data to generate a reduced set of (compressed) data from which the original image can be reconstructed without loss of essential features. The compressed data can be transmitted (or stored) more efficiently than can the original image data. An inverse (decompression) transformation can be applied to the transmitted data (or the data read out from storage) to recover the original image (or a reasonable facsimile thereof).
Throughout this specification, including in the claims, "block" denotes an array of N.times.M samples of a given color component (N and M are integers), "word" denotes a color component sample (e.g., an analog red, green, or blue sample of an analog image representation, or an eight-bit digital word defining a red, green, or blue sample of an analog image representation), and "line length" denotes the number of words per line of an image signal (for the color component having the highest horizontal resolution, in the case of color image data in which the different color components have different resolution).
Most image compression algorithms do not process image data in line-scan format, and instead process image data in N'.times.M' block format. For example, the conventional image compression algorithms known as the ISO "JPEG" algorithm (for still images) and the ISO "MPEG" algorithm (for video signal compression) both process image data in 8.times.8 block format (M'=N =8). Examples of such input data include: a repeating sequence of an 8.times.8 block of red words, followed by an 8.times.8 block of green words, followed by an 8.times.8 block of blue words (image processors for processing "RGB(1:1:1)" images will expect the input data to have this format); and a repeating sequence of two 8.times.8 blocks of Y words, followed by an 8.times.8 block of U words, followed by an 8.times.8 block of V words (image processors for processing "YUV(2:1:1)" images will expect the input data to have this format).
Typical algorithms for performing image compression on digital image data include two steps: a transformation step which generates transformed image data (in which the correlation between adjacent pixels is reduced relative to that existing in the input image data); followed by a quantization step which replaces each pixel of the transformed image data with a quantized pixel comprising fewer bits (on the average). To reduce loss of information during the quantization step, it has been proposed to design the transformation step so that the transformed image data is a set of component image signals having different spatial frequencies (so that the transformed image data is a "pyramidal" or "multiresolution" representation of the image).
For example, U.S. Pat. No. 5,014,134, issued May 7, 1991, discloses a method and apparatus for performing image compression in which image data are transformed into a pyramidal image representation. The apparatus of U.S. Pat. No. 5,014,134 includes a first transformation circuit ("analyzer") which converts each row of an M.times.M block of input image data into two vectors, y.sub.L and y.sub.H, each comprising M/2 words. Vectors y.sub.L define an M row.times.M/2 column component image representation L (representing relatively low spatial frequency information), and vectors y.sub.H define an M.times.M/2 component image representation H (representing relatively high spatial frequency information). The apparatus of U.S. Pat. No. 5,014,134 includes two additional analyzers. One of the additional analyzers (the "second" analyzer) receives a sequence of column vectors of image L and converts each such column vector into two column vectors y.sub.LL and y.sub.LH (each comprising M/2 words). The other of the additional analyzers (the "third" analyzer) receives a sequence of column vectors of image H and converts each such column vector into two column vectors y.sub.HL and y.sub.HH (each comprising M/2 words). The outputs of the second analyzer determine two M/2.times.M/2 component images (LL and LH), and the outputs of the third analyzer determine two M/2.times.M/2 component images (HL and HH). Image LL represents the lowest spatial frequency information of the original image, and images LH, HL, and HH represent higher spatial frequency information of the original image. Component images LL, LH, HL, and HH (each of which is a M/2.times.M/2 image data block, and which together define a pyramidal representation of the original image) are then separately quantized and coded to generate compressed image data representing a compressed version of the original image.
The upper left image representation, I, in FIG. 1 represents the original image, the upper right image representation in FIG. 1 represents component images L and H, and the lower left image representation in FIG. 1 represents component images LL, LH, HL, and HH (which together define a pyramidal representation of the original image).
The apparatus of U.S. Pat. No. 5,014,134 also discloses means for reconstructing the original image, which generates one M.times.M block of reconstructed image data from the compressed image data. The reconstruction means includes a dequantizer and decoder for reconstructing the M/2.times.M/2 component image representations LL, LH, HL, and HH from the compressed image data, and three transformation circuits ("synthesizers"). The first synthesizer transforms the reconstructed (decompressed) HH and HL component images into a reconstructed image representation H (an M.times.M/2 component image representation). The second synthesizer transforms the reconstructed (decompressed) LH and LL component images into a reconstructed image representation L (also an M.times.M/2 component image representation). The third synthesizer receives the reconstructed image representations L and H, and transforms them into a reconstructed image representation (an M.times.M representation of the original image).
U.S. Pat. No. 5,014,134 also teaches an iterative pyramidal representation generation process, in which each iteration consists of transforming the component image representation having the lowest spatial frequency (the LL component image representation) generated during previous iteration. The lower right image representation of FIG. 1 represents the result of performing a second iteration of this type on the lower left image representation of FIG. 1. Specifically, the lower right image in FIG. 1 represents component images LLLL, LLHL, LLLH, LLHH, LH, HL, and HH (which together define a pyramidal representation of the original image, with component images LLLL, LLHL, LLLH, LLHH together defining a pyramidal representation of component image LL generated during the first iteration).
However, the methods and apparatus disclosed in U.S. Pat. No. 5,014,134 for transforming image data into pyramidal representations do not result in pyramidal representations optimal for subsequent quantization and coding (particularly for coding in accordance with the conventional ISO "JPEG" or "MPEG" image compression algorithm).